//
//  204. 计数质数.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/1/31.
//

import Foundation

// 给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

func isPrime1(_ x: Int) -> Bool {
    for index in 2..<x where index * index <= x {
        if x % index == 0 {
            return false
        }
    }
    return true
}

func isPrime(_ x: Int) -> Bool {
    if x <= 1 {
        return false
    }
    if x <= 3 {
        return true
    }
    var i = 2
    while i * i <= x {
        if x % i == 0 {
            return false
        }
        i += 1
    }
    return true
}

func getPrimes(_ n: Int) -> Int {
    var ans = 0
    for index in 2..<n {
        ans += isPrime(index) ? 1 : 0
    }
    return ans
}

func countPrimes(_ n: Int) -> Int {
    guard n > 2 else {
        return 0
    }
    var isPrime = [Bool](repeating: true, count: n)
    var count = 0

    for i in 2..<n {
        if isPrime[i] {
            count += 1
            var j = 2
            while i * j < n {
                isPrime[i * j] = false
                j += 1
            }
        }
    }
    return count
}

func countPrimes1(_ n: Int) -> Int {
        var primes = [Int]()
        var isPrime = [Int](repeating: 1, count: n)
        for i in 2..<n {
            if isPrime[i] == 1 {
                primes.append(i)
            }
            var j = 0
            while j < primes.count && i * primes[j] < n {
                isPrime[i * primes[j]] = 0
                if i % primes[j] == 0 {
                    break
                }
                j += 1
            }
        }
        return primes.count
    }

